Graph / Chordal graph (Bibtex)

P270: Enumeration of all chordal graphs in a graph

Input:

A graph $G$.

Output:

All chordal graphs in $G$.

Complexity:

$O(1)$ delay with $O(n^3)$ space.

Comment:

Using reverse search.

Reference:

[Kiyomi2006] (Bibtex)

P272: Enumeration of all chordal supergraph that contains a given graph

Input:

A graph $G = (V, E)$.

Output:

All chordal supergraphs each of which contain $G$.

Complexity:

$O(|V|^3)$ time for each and $O(|V|^2)$ space.

Comment:

Reference:

[Kiyomi2006a] (Bibtex)

P213: Enumeration of all chordal sandwiches in a graph

Input:

A graph $G = (V, E)$.

Output:

All chordal sandwiches in $G$.

Complexity:

Polynomial delay with polynomial space.

Comment:

Reference:

[Kijima2010] (Bibtex)

P509: Enumerate all maximal chordal induced graphs in a graph

Input:

A graph $G=(V, E)$.

Output:

All maximal chordal induced graphs in $G$.

Complexity:

$O(|E|^2|V|)$ delay.

Comment:

Exponential space. Proximity search.

Reference:

[Conte2019] (Bibtex)

P510: Enumerate all maximal connected chordal induced graphs in a graph

Input:

A graph $G=(V, E)$

Output:

All maximal connected chordal induced graphs in $G$.

Complexity:

$O(|E|^2|V|)$ delay.

Comment:

Exponential space. Proximity search.

Reference:

[Conte2019] (Bibtex)